<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 1. Геометрия.2D.base</h2>
<ol>
  <li>Скалярное и векторное произведение</li>
  <ol>
    <li>Вычисление, формулы через cos и sin</li>
    <li>Величина угла между векторами = atan2</li>
    <li>Насколько малым может быть угол, если координаты до 10<sup>9</sup>?</li>
  </ol></li>
  <li>Нормировка векторов</li>
  <ol>
    <li>Расстояние до прямой</li>
    <li>Биссектриса угла</li>
  </ol></li>
  <li>Сортировка по углу</li>
  <ol>
    <li>Угол разворота меньше PI: векторное произведение</li>
    <li>Угол разворота больше: честно считаем atan2</li>
    <li>Векторное произведение: x<sub>1</sub>y<sub>2</sub> - x<sub>2</sub>y<sub>1</sub> &gt; eps</li>
    <li>Не существует корректного eps (т.е. Fib<sub>n</sub>Fib<sub>n+2</sub> - Fib<sub>n+1</sub><sup>2</sup> = &pm;1)</li>
    <li>Поделим на длину. Получим sin(a). Длину нужно предподсчитать (т.к. sqrt долгий)</li>
  </ol></li>
  <li>Окружности</li>
  <ol>
    <li>Пересечение окружностей</li>
    <li>Касательной от точки к окружности: сведение к пересечению окружностям</li>
    <li>Общие касательные к окружностям: сведение к касательной от точки к окружности</li>
    <li>Общие касательные к окружностям: решение без сведений</li>
  </ol></li>
  <li>Вычисление площади</li>
  <ol>
    <li>За O(n) + доказательство</li>
    <li>Задача про количество черных клеток шахматной доски, покрытых прямоугольным многоугольником</li>
  </ol></li>
  <li>Выпуклая оболочка</li>
  <ol>
    <li>Грэхем [сортировка + стэк] за O(nlogn)</li>
    <ol>
      <li>Выбор первой точки</li>
      <li>Сортировка по углу</li>
      <li>Сортировка по расстоянию</li>
    </ol></li>
    <li>Джарвис [заворачивание подарка] за O(nk)</li>
  </ol></li>
  <li>Расстояния</li>
  <ol>
    <li>Расстояние между точками (а за одно в d-мерном пространстве)</li>
    <li>От точки до отрезка (а за одно в d-мерном пространстве)</li>
    <li>Между отрезками</li>
    <li>От круга до отрезка</li>
    <li>Расстояние от точки до квадрата</li>
    <li>Между выпуклыми многоугольниками за O(n<sup>2</sup>)</li>
    <li>Расстояние от круга до квадрата</li>
  </ol></li>
  <li>Проверка, лежит ли точка внутри многоугольника</li>
  <ol>
    <li>Пускаем луч за O(n)</li>
    <li>Крайние случаи: рандомный луч</li>
    <li>Крайние случаи: а луч все равно горизонтальный (без лишних if-ов)</li>
  </ol></li>
  <li>Пересечение</li>
  <ol>
    <li>Двух отрезков</li>
    <li>Двух треугольников</li>
  </ol></li>
</ol>
